﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    //==================================力扣226 翻转二叉树
    //思路：即是交换所有节点的左右子节点即可
    //还是需要遍历二叉树，但不能采用中序遍历，会造成某些子节点交换两次
    class FlipTree
    {
        //=======================递归法
        public TreeNode InvertTree(TreeNode root)
        {
            //递归前序遍历
            if (root == null)
                return root;
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;//中
            InvertTree(root.left);//左
            InvertTree(root.right);//右
            return root;
        }

        //=======================迭代法
        public TreeNode InvertTree_2(TreeNode root)
        {//深度优先遍历
            if (root == null)
                return root;

            Stack<TreeNode> st = new Stack<TreeNode>();
            st.Push(root);
            while(st.Count > 0)
            {
                TreeNode node = st.Pop();//中

                TreeNode tmp = node.left;
                node.left = node.right;
                node.right = tmp;

                if (node.right != null)
                    st.Push(node.right);//右
                if (node.left != null)
                    st.Push(node.left);//左
            }
            return root;
        }

        //======================== 层序遍历
        public TreeNode InvertTree_3(TreeNode root)
        {//广度优先遍历
            Queue<TreeNode> que = new Queue<TreeNode>();

            if (root != null)
                que.Enqueue(root);

            while(que.Count > 0)
            {
                int size = que.Count;
                for(int i = 0;i<size;i++)
                {
                    TreeNode node = que.Dequeue();

                    TreeNode tmp = node.left;
                    node.left = node.right;
                    node.right = tmp;

                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
            }
            return root;

        }
    }
}
